import pgzrun
from vec import *
import random
import time

WIDTH = 600
HEIGHT = 440

BACK_COLOR = (0, 0, 0)
PEN_COLOR = (0, 200, 0)

lastTime = time.time()
deltaTime = 0

rcHeight = [100, 200, 120, 80, 50, 150, 20, 160, 90, 130]

n = len(rcHeight)
rcWidth = 20
space = 10
pspd = 0.5

class MyRect:
    def __init__(self, lb_x, lb_y, h, clr):
        self.pos = Vec2(lb_x, lb_y)
        self.h = h
        self.clr = clr
        self.p = 0.0
        self.curState = 0   # 0: 静止，1: 移动
        self.start_pt = Vec2(0, 0)
        self.end_pt = Vec2(0, 0)

    def StartMove(self, end_pt):
        if self.curState == 1:
            return

        self.curState = 1
        self.p = 0
        self.start_pt = self.pos
        self.end_pt = end_pt

    def Move(self):
        has_finished = False

        self.p += pspd * deltaTime

        if self.p > 1.0:    
            self.p = 1.0
            has_finished = True

        self.pos = self.start_pt * (1 - self.p) + self.end_pt * self.p

        return has_finished

    def Update(self):
        if self.curState == 1:
            if self.Move() == True:
                self.curState = 0

    def Draw(self):
        rc = Rect((self.pos.x, self.pos.y - self.h), (rcWidth, self.h))
        screen.draw.filled_rect(rc, self.clr)

def shell_sort(lst):
    length = len(lst)
    if length <= 1:
        return lst

    sorted_list = lst
    gap = length // 2
    while gap > 0:
        for i in range(gap, length):
            j = i - gap
            temp = sorted_list[i]
            while j >= 0 and temp < sorted_list[j]:
                sorted_list[j + gap] = sorted_list[j]
                j -= gap
            sorted_list[j + gap] = temp
        gap //= 2
    return sorted_list

startX = 150
iter = startX
rcList = []

isSortingFinished = False
sortingState = 0  # 0: 交换数据，1: 移动矩形

for item in rcHeight:
    r = random.randint(50, 200)
    g = random.randint(50, 200)
    b = random.randint(50, 200)
    rcList.append(MyRect(iter, HEIGHT / 2, item, (r, g, b)))
    iter += rcWidth
    iter += space


shell = []




shell_sort(rcHeight)
i = 0
sortStack = []

def update():
    global lastTime, deltaTime, isSortingFinished, sortingState
    global i, sortStack, lastSpace, shell
    curTime = time.time()
    deltaTime = curTime - lastTime
    lastTime = curTime

    if isSortingFinished == True:
        return

    if sortingState == 0:
        if i >= len(shell):
            isSortingFinished = True
        else:
            n = len(sortStack)
            if n >= 2 and \
               shell[i][0] == sortStack[n - 2][0] and \
               shell[i][1] == sortStack[n - 1][1]:
                lo, hi, lstmIndex = merge(rcHeight, sortStack[n - 2][0], sortStack[n - 1][0], sortStack[n - 1][1])
                sortStack.pop()
                sortStack.pop()

                dirty = False
                rclst = []
                for j in range(len(lstmIndex)):
                    idx = lstmIndex[j]
                    if idx != lo + j:
                        rcList[idx].StartMove(rcList[lo + j].pos)
                        dirty = True

                    rclst.append(rcList[idx])

                if dirty == True:
                    rcList[lo:hi] = rclst

                    sortingState = 1

            sortStack.append(shell[i])

            i += 1
    else:
        allStoped = True
        for rc  in rcList:
            rc.Update()
            if rc.curState == 1:
                allStoped = False

        if allStoped == True:
            sortingState = 0

def draw():
    screen.clear()
    screen.fill(BACK_COLOR)
    screen.draw.line((0, HEIGHT / 2), (WIDTH, HEIGHT / 2), PEN_COLOR)
    for rc in rcList:
        rc.Draw()

pgzrun.go()